Missing number in arithmetic progression

Time: O(LogN); Space: O(1); easy

In some array arr, the values were in arithmetic progression:

the values arr[i+1] - arr[i] are all equal for every 0 <= i < arr.length - 1.

Then, a value from arr was removed that was not the first or last value in the array.

Return the removed value.

Example 1:

Input: arr = [5,7,11,13]

Output: 9

Explanation:

• The previous array was [5,7,9,11,13].

Example 2:

Input: arr = [15,13,12]

Output: 14

Explanation:

• The previous array was [15,14,13,12].

Constraints:

• 3 <= len(arr) <= 1000

• 0 <= arr[i] <= 10^5

1. Binary Search [O(LogN), O(1)]

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        def check(arr, d, x):
            return arr[x] != arr[0] + d*x

        d = (arr[-1]-arr[0])//len(arr)
        left, right = 0, len(arr)-1
        while left <= right:
            mid = left + (right-left) // 2
            if check(arr, d, mid):
                right = mid - 1
            else:
                left = mid + 1

        return arr[0] + d*left

s = Solution1()

arr = [5,7,11,13]
assert s.missingNumber(arr) == 9

arr = [15,13,12]
assert s.missingNumber(arr) == 14

2. Binary Search [O(), O()]

class Solution2(object):
    """
    Time: O()
    Space: O()
    """
    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        return (min(arr) + max(arr)) * (len(arr) + 1) // 2 - sum(arr)

s = Solution2()

arr = [5,7,11,13]
assert s.missingNumber(arr) == 9

arr = [15,13,12]
assert s.missingNumber(arr) == 14

See also:

https://leetcode.com/problems/missing-number-in-arithmetic-progression